package Dynamic_Program;

//https://leetcode.cn/problems/climbing-stairs/submissions/494748176/?envType=study-plan-v2&envId=top-100-liked

public class Clambing_stairs {
        public static int solution(int n) {
            int[] arr = new int[n+3]; // 定义
            // 可以拆分成两部分之和，最后一步要跨1个台阶还是两个台阶
            // 如果是一个台阶，那么就是arr[i-1];
            // 如果是两个台阶，那么就是arr[i-2];

            //初始化
            arr[0] = 1;
            arr[1] = 1;
            if(n==1){
                return 1;
            }
            for (int i=2;i<=n;i++){
                arr[i] = arr[i-1] + arr[i-2];
            }
            return arr[n];
        }

}
